﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

// The graph is represented by the vertices list principle. 
// Here it is implemented as a list of nodes (Vertex) and every node contains a list of edges. (Edge).

namespace Noea.Graph
{

    // Implements IGraph using Adjacency Lists.

    public class BasicGraph : IBasicGraph
    {
        private Dictionary<string, Vertex> vertices;
		
		public BasicGraph()
		{
            vertices = new Dictionary<string, Vertex>();
        }

		public void AddVertex(Vertex vertex)
		{
            if (GetVertexByName(vertex.Name) != null) return;
            vertices[vertex.Name] = vertex;
		}

        public Vertex GetVertexByName(string name)
        {
            if (vertices.ContainsKey(name))
                return vertices[name];
            return null;
        }

		public void AddEdge(Vertex startVertex, Vertex endVertex)
		{
            startVertex.AddEdgeTo(endVertex);
		}

		public void RemoveEdge(Vertex startVertex, Vertex endVertex)
		{
            startVertex.RemoveEdgeTo(endVertex);
		}

		public bool ContainsVertex(Vertex vertex)
		{
            return vertices.Values.Contains(vertex);
		}

		///<summary>
		///determines whether two vertices are adjacent
		///</summary>
		public bool IsAdjacent(Vertex startVertex, Vertex endVertex)
		{
            return startVertex.EdgeTo(endVertex) != null;
		}

		///<summary>
		///Returns a list containing all vertices adjancent to vertex.
		///Must be a list since it should be possible to remove adjacent vertices
		///</summary>
		public IList<Vertex> GetAdjacencies(Vertex vertex)
		{
            IList<Vertex> adj = new List<Vertex>();
            foreach (Edge edge in vertex.Edges())
            {
                adj.Add(edge.To);
            }
            return adj;
		}

		public Dictionary<string, Vertex> Vertices
		{
			get
			{
				return vertices;
			}
		}

		///<summary>
		///determines whether the graph is empty
		///</summary>
		public bool IsEmpty()
		{
			return vertices.Count == 0;
		}

		///<summary>
		///returns the number of vertices
		///</summary>
		public int GetNoOfVertices()
		{
			return vertices.Count;
		}

		///<summary>
		///returns the number of edges
		///</summary>
		public int GetNoOfEdges()
		{
			int nrOfEdges = 0;
            foreach(Vertex vertex in vertices.Values.ToArray()) nrOfEdges += vertex.Edges().Count;
			return nrOfEdges;
		}

		public List<Edge> Edges
		{
			get
			{
				List<Edge> edges = new List<Edge>();
				foreach(Vertex vertex in vertices.Values.ToArray())
					foreach (Edge edge in vertex.Edges())
						if (!edges.Contains(edge))
							edges.Add(edge);

				return edges;
			}
		}

		public void printTree(Vertex startVertex, string intend = "", List<Vertex> visited = null)
		{
            if (visited == null) visited = new List<Vertex>();
            Console.WriteLine(intend + startVertex.Name);
            if (visited.Contains(startVertex)) return;
            visited.Add(startVertex);
            intend += "    ";
            foreach (Vertex vertex in GetAdjacencies(startVertex))
            {
                printTree(vertex, intend);
            }
		}

		///<summary>
		///makes the graph empty
		///</summary>
		public void Clear()
		{
            vertices.Clear();
		}

		public void Bfs(Vertex v)
		{
			List<Vertex> que = new List<Vertex>();
			v.Visited = true;
			que.Add(v);

			while (que.Count != 0)
			{
				Vertex w = que[0];
				que.Remove(que[0]);

				foreach (Vertex vertex in GetAdjacencies(w))
				{
					if (!vertex.Visited)
					{
						//Console.WriteLine(vertex.Name);
						vertex.Visited = true;
						que.Add(vertex);
					}
				}
			}
		}
		
		public void Dfs(Vertex v)
		{
			v.Visited = true;

			foreach (Vertex vertex in GetAdjacencies(v))
				if (!vertex.Visited)
				{
					dfsResult.Add(vertex);
					//Console.WriteLine(vertex.Name);
					Dfs(vertex);
				}
		}

		private IList dfsResult = new List<Vertex>();
		
		public IList DepthFirstSearch(Vertex v)
		{
			dfsResult.Clear();
			Unmark();
			Dfs(v);
			return dfsResult;
		}

		public void Unmark()
		{
			foreach (Vertex vertex in vertices.Values.ToArray())
				vertex.Visited = false;
		}
	}
}

